#include <iostream>
#include <sstream>
#include <string>
#include <queue>
using namespace std;

struct Node {
	string val;
	Node* left = nullptr;
	Node* right = nullptr;
};
string sp;
Node* A = nullptr;
int c = 0;
void getTree(Node*& h)
{
	h = new Node;
	queue<Node*> q;
	string line;
	getline(cin, line);
	stringstream ss(line);
	ss >> h->val; c++;
	q.push(h);
	while (q.size()) {
		Node* cur = q.front(); q.pop();
		string l, r;
		if (!(ss >> l))break;
		if (l != sp) {
			cur->left = new Node;
			cur->left->val = l;
			q.push(cur->left);
			c++;
		}
		if (!(ss >> r))break;
		if (r != sp) {
			c++;
			cur->right = new Node;
			cur->right->val = r;
			q.push(cur->right);
		}
	}
}
#include <climits>
int ans = INT_MIN;

int getL(Node* h)
{
	if (!h) return 0;
	int l = getL(h->left);
	int r = getL(h->right);
	ans = max(l + r + 1, ans);
	return 1 + max(l, r);
}

void i(Node* h, int l, string val)
{
	queue<Node*> q;
	q.push(h);
	for(int i = 1; i < l; i++)
	{
		int k = q.size();
		while (k--) {
			if (i == l - 1) {
				auto cur = q.front(); q.pop();
				Node* l = new Node;
				Node* r = new Node;
				l->left = cur->left;
				cur->left = l;
				r->right = cur->right;
				cur->right = r;
				l->val = r->val = val;
				++++c;
			}
			else {
				auto cur = q.front(); q.pop();
				if (cur->left) q.push(cur->left);
				if (cur->right) q.push(cur->right);
			}
		}
	}
}

void p(Node* h)
{
	queue<Node*> q;
	q.push(h);
	while (q.size()) {
		auto cur = q.front(); q.pop();
		if (cur == nullptr) {
			if (c == 0) return;
			cout << "null ";
			continue;
		}
		c--;
		cout << cur->val << ' ';
		q.push(cur->left);
		q.push(cur->right);
	}
}

int main()
{
	getline(cin, sp);
	sp = "null";
	getTree(A);


	string val; cin >> val;
	int l; cin >> l;
	if (l != 1) i(A, l, val), p(A);
	else {
		cout << "1 1 null ";
	}

	return 0;
}
//4
//2 n
//3 1
//
//4
//2 n
//1 1 
//3 n n 1